/*
 * =====================================================================================
 *
 *       Filename:  rotate.cpp
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  02/22/2011 11:44:19 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Ken Chen (Ken), chen_kenz@emc.com
 *        Company:  EMC
 *
 * =====================================================================================
 */

#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
#include <cassert>

using namespace std;

void right_rotate(int* arr, int n, int k)
{
  if(k < 1)
  {
    return;
  }

  int itemsInWrongPlace = n;
  int* boundary = arr + (n-k);
  int* current = arr;
  int i = 0;
  while(itemsInWrongPlace > 0)
  {
    // each step, place k items in the right place
    for(i = 0; (current != boundary) && (i < k); ++i)
    {
      swap(*current++, *(arr+n-k+i));
    }
    itemsInWrongPlace -= i;

    if(current == boundary)
    {
      right_rotate(current, k, k - i);
      itemsInWrongPlace -= k;
    }
  }
}

int main(int argc, char* argv[])
{
  int n = 10000;
  int k = 4000; 
  vector<int> vi;
  vi.reserve(10000);
  for(int i = 0; i < n ; ++i)
  {
    vi.push_back(i);
  }

  //vector<int> vii(vi);

  for(int m = 0; m < 10000; ++m)
  {
    //rotate(vi.begin(), vi.begin() + n - k, vi.end());
    right_rotate(&(*vi.begin()), vi.size(), k);
  }

#if 0
  for(int j = 0; j < n; ++j)
  {
    if(j < k)
    {
      assert(vi[j] == (j + n - k)); 
      assert(vii[j] == (j + n - k)); 
    }
    else
    {
      assert(vi[j] == (j - k));
      assert(vii[j] == (j - k));
    }
  }
#endif 
}
